| 离散数学实验1 可图画，可简单图化，连通图和欧拉图的判断 C++ | 您所在的位置：网站首页 › 简单的 图画 › 离散数学实验1 可图画，可简单图化，连通图和欧拉图的判断 C++ |
离散数学实验1 可图画，可简单图化，连通图和欧拉图的判断 C++
|
离散数学实验报告
文章目录
离散数学实验报告一、实验题目二、实验目的三、实验要求四、实验步骤和内容需求分析：输入形式与输入范围
概要设计：使用的数据结构与算法：程序流程：
详细代码调试分析调试过程中所遇到的问题及解决方法算法的时空分析
五、实验结果六、实验总结
一、实验题目
实验题目：可图画，可简单图化，连通图和欧拉图的判断 实验时间: 2021.12.9 二、实验目的掌握可简单图化的定义及判断方法 掌握连通图、欧拉图的判断方法 掌握欧拉回路的搜索方法 了解欧拉图的实际应用 三、实验要求给定一非负整数序列（例如：(4,2,2,2,2)） 判断此非负整数序列是否是可图化的，是否是可简单图化的 如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此简单图的相邻矩阵（默认第i行对应顶点vi） 判断此简单图是否是连通的 如果是连通图，判断此图是否是欧拉图。如果是欧拉图，请输出一条欧拉回路（输出形式如： v 2 − v 1 − > v 5 − > v 3 − > v 4 − > v 5 − > v 2 v_2-v_1->v_5->v_3->v_4->v_5->v_2 v2−v1−>v5−>v3−>v4−>v5−>v2 四、实验步骤和内容 需求分析：对一个度数列判断是否可图化，若可图化则继续判断是否可简单图化，若可简单图化判断是否为欧拉 图，若为欧拉图则输出欧拉回路 输入形式与输入范围预设输入点范围 : 0 < n < 999 0V1 概要设计： 使用的数据结构与算法： 相邻矩阵、深度优先遍历、栈、fleury算法 程序流程：拿到度数列根据度数列之和是否为偶数（握手定理）判断是否可图化，若不可图化程序退出。并且同时判断有无奇数度的点，为判断是否为欧拉图做准备。 若可图化，利用定理4（ check()函数 ）判断是否可简单图化，否则退出程序。 若可简单图化，在Havel定理（ simple()函数 ）运行的过程建立相邻矩阵。 输出相邻矩阵 用深度优先遍历（ bfs()函数 ）判断是否为连通图，并且求出连通分支个数。 若为连通图，根据之前的结果判断是否为欧拉图，反之程序退出 若为欧拉图，利用Fleury算法输出欧拉回路，取第一个点，然后遍历与其连通的边，并判断此边是否为桥，若不为桥则走过这条边，并将其从图中删除，然后对下一个点进行同样的操作，如此递归。注：因为判断是否为桥的时间复杂度太高，我使用了另外一种方法来优化该算法，具体思路如下：
如上图，显然奇数出度的点为1和2，于是我们选择一个点，比如说选择1，那么我们在dfs的过程中，按照dfs的顺序把点的编号放进栈中，比如我们的访问次序是12432，则把12432放入栈中，每经过一条边，就把这条边的正向边反向边打上标记表示这条路已经走过了，由于之前我们已经判过欧拉回路存在的充要条件了，所以请对这张图保持信心，一定是可以找到欧拉回路的，于是我们的算法流程就是： 先把1放到栈中，然后把1-2的边的正向边反向边打上标记，表示已经走过了，然后再把2放到栈中，然后走2-4，打标记，4入栈，走4-3，打标记，3入栈，走3-2，打标机，2入栈，然后我们去走2的时候发现2已经无路可走了，她能走的所有边已经被打上了标记，也就是说这个点已经没有办法出去了，那么什么样的点进去了出不来呢？显然就是我们的奇数出度的点，于是我们在这里把栈顶输出，然后pop出去，然后回溯，每回溯到一个点都判断这个点是否还能走其他边，如果不能走的话，我们就输出这个点，然后再回溯，一直到一个点有其他边可以走，我们就把这个pop，但是不输出，然后再重新从这个点开始dfs比如说这幅图中，我们在dfs了2及右边之后，左边的1由于还有边可以走，于是不输出，从1再开始dfs，最后输出的序列就是2 , 4 , 3，2，1，5 , 6 , 1 详细代码 #include #include #include #include using namespace std; int ans[1000]; int idxx; int sq[1000][1000]; pair d[1000]; pair d2[1000]; bool st[1000]; vector isin; bool isol= true; int l=1; int sum=0; stackstk; void search(int x){ stk.push(x); for(int i=1;i sq[i][x]=sq[x][i]=0; search(i); break; } } } void dfs(int x){ if(st[x]) return; st[x]= true; for(int i=1;i int lf,rt; for(int i=1;i lf+=d[j].first; } rt=i*(i-1); for(int j=i+1;j for(int i=1;i sq[d[i+j].second][d[i].second]=sq[d[i].second][d[i+j].second]=1; d[j+i].first--; } sort(d+i+1,d+l+1,greater()); } printf(" "); for(int i=1;i printf("V%d ",i); for(int j=1;j stk.push(x); while(!stk.empty()){ int brg=0; for(int i=1;i brg=1; break; } } if(!brg){ printf("->V%d",stk.top()); stk.pop(); }else { int nw=stk.top(); stk.pop(); search(nw); } } printf("\n"); } int main() { while(1){ cout cout cout fr++; dfs(i); } } if(fr==1){ printf("\n连通\n"); memset(st,0,sizeof st); if(isol){ printf("\n是欧拉图，它的一条欧拉回路是："); // isin.push_back(1); while(stk.size()) stk.pop(); fleury(1); }else{ printf("不是欧拉图"); } }else{ printf("不连通，连通分支数为%d\n",fr); continue; } }else{ cout |
【本文地址】
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |